package com.tim.test.leetcode.algorithm;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * 数据结构
 */
public class DataStructure {

    int[] arr;
    ArrayList list1;
    Stack stack;// 栈，数组实现
    // 双向链表。remove(1)移除指定索引元素
    LinkedList linkedList;// remove o(n)
    PriorityQueue<Integer> priorityQueue;// 默认小根堆
    // 链表、图

    class O1LinkedList {
        Node head;
        Node tail;

        class Node {
            Node pre;
            Node next;
            int key;
        }
    }

    /**
     * 最大堆
     */
    static class MaxHeap {
        private int[] eles;
        private int usedSize;

        public MaxHeap() {
            init(10);
        }

        private void init(int size) {
            eles = new int[size];
            usedSize = 0;
        }

        /**
         * 将一棵树调整为大堆的思路
         * 1，每颗子树都应该变成大堆
         * 2，从最后一颗子树开始调整
         * <p>
         * 步骤
         * 1，定义子树父节点p，子节点c
         * 2，在父节点左右两边，找到左右孩子的最大值
         * 3，让左右孩子的最大值，和父节点进行交换
         * 4，迭代调整
         */
        public void createHeap(int[] arr) {
            init(arr.length);
            for (int i = 0; i < arr.length; i++) {
                // 数组值拷贝给eles
                eles[i] = arr[i];
                usedSize++;
            }
            // 最后一个节点下标arr.length-1；父节点下标：(arr.length-1-1)/2
            for (int parent = (arr.length - 2) / 2; parent >= 0; parent--) {
                // 每次调整的结束位置：不超过数组下标最大值
                adjustDown(parent, usedSize);
            }

        }

        // root父节点索引值，len数组长度
        private void adjustDown(int root, int len) {
            int parent = root;
            int child = 2 * parent + 1;

            while (child < len) {// 存在左子节点，为非叶节点

                // 若右子节点存在；获取子节点最大值
                if (child + 1 < len && eles[child] < eles[child + 1]) {
                    child++;
                }

                if (eles[child] > eles[parent]) {
                    // 子节点最大值大于父节点值，交换
                    swap(eles, child, parent);
                    // 处理交换后子树
                    parent = child;
                    child = 2 * parent + 1;
                } else {
                    break;
                }

            }

        }

        private void swap(int[] arr, int i, int j) {
            if (i == j) {
                return;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        public void push(int val) {
            ensureCapacity();
            eles[usedSize] = val;
            usedSize++;
            adjustUp(usedSize - 1);
        }

        private void ensureCapacity() {
            if (eles.length == usedSize) {
                eles = Arrays.copyOf(eles, eles.length * 2);
            }
        }

        // 上浮
        private void adjustUp(int child) {
            int parent = (child - 1) / 2;
            while (child > 0) {
                if (eles[child] > eles[parent]) {
                    // cVal>pVal，交换c、p值；
                    swap(eles, child, parent);
                    // 处理祖级树
                    child = parent;
                    parent = (child - 1) / 2;
                } else {
                    break;
                }
            }
        }

        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException();
            }
            int num = eles[0];
            swap(eles, 0, usedSize-1);
            usedSize--;
            // 除顶层树外，顺序均正常；顶层树下沉即可
            adjustDown(0, usedSize);
            return num;
        }

        private boolean isEmpty() {
            return usedSize == 0;
        }

        public int peek(){
            if (isEmpty()) {
                throw new RuntimeException();
            }
            int num = eles[0];
            return num;
        }
    }

    public static void main(String[] args) {
        int[] arr = new Random()
                .ints(20, 1, 100)
                .toArray();
        System.out.println(JSON.toJSONString(arr));
        MaxHeap heap = new MaxHeap();
        heap.createHeap(arr);
        System.out.println(heap.pop());
        heap.push(100);
        System.out.println(heap.pop());
    }
}
